package q0092.reverseList2;


/**
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 * <p>
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *  
 * <p>
 * 提示：
 * <p>
 * 链表中节点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 *  
 * <p>
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author fangjiaxiaobai
 * @date 2021-08-29 17:46
 */
public class Solution {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 非空判断
        if (null == head || null == head.next || left == right) {
            return head;
        }

        // preReverseNode: 开始反转节点的前一个节点
        // endReverseNode: 结束反转的节点
        ListNode preReverseNode = null, start1Node = head;
        ListNode preNode = null, curNode = null;
        ListNode newHeadNode = head;

        // 遍历节点的个数
        int index = 1;

        while (null != head) {
            // 遍历到开始反转的节点
            if (index < left) {
                preReverseNode = head;
                head = head.next;
            } else if (index == left) {
                curNode = head.next;
                preNode = head;
                head = head.next;
                preNode.next = null;
            } else if (index <= right) {
                curNode = head;
                // 反转
                ListNode tempNode = curNode.next;
                curNode.next = preNode;
                preNode = curNode;
                curNode = tempNode;
                head = tempNode;
                if (null == preReverseNode) {
                    newHeadNode = preNode;
                }
            } else {
                break;
            }
            index++;
        }

        // 1.拼接后节点
        if (null != preReverseNode) {
            preReverseNode.next.next = curNode;
            preReverseNode.next = preNode;
        } else {
            start1Node.next = curNode;
        }
        return newHeadNode;
    }

    public static void main(String[] args) {
        demo1();
        demo2();
    }

    private static void demo2() {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        head.next = node2;
        ListNode node3 = new ListNode(3);
        node2.next = node3;

        print(head);

        ListNode listNode = new Solution().reverseBetween(head, 2, 3);

        print(listNode);
    }

    private static void demo1() {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        head.next = node2;
        ListNode node3 = new ListNode(3);
        node2.next = node3;
        ListNode node4 = new ListNode(4);
        node3.next = node4;
        ListNode node5 = new ListNode(5);
        node4.next = node5;

        print(head);

        ListNode listNode = new Solution().reverseBetween(head, 2, 4);

        print(listNode);
    }

    public static void print(ListNode listNode) {
        while (listNode != null) {
            System.out.printf("%d\t", listNode.val);
            listNode = listNode.next;
        }
        System.out.println();
    }
}
